{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Symmetric Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isSymmetric"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #对称二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二叉树的根节点 <code>root</code> ， 检查它是否轴对称。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://pic.leetcode.cn/1698026966-JDYPDU-image.png\" style=\"width: 354px; height: 291px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,2,3,4,4,3]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://pic.leetcode.cn/1698027008-nPFLbM-image.png\" style=\"width: 308px; height: 258px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,2,null,3,null,3]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[1, 1000]</code> 内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以运用递归和迭代两种方法解决这个问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [symmetric-tree](https://leetcode.cn/problems/symmetric-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [symmetric-tree](https://leetcode.cn/problems/symmetric-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,3,4,4,3]', '[1,2,2,null,3,null,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def helper(self, l, r):\n",
    "        if l is None and r is None:\n",
    "            return True\n",
    "        if l is None or r is None:\n",
    "            return False\n",
    "        if l.val != r.val:\n",
    "            return False\n",
    "        \n",
    "        return self.helper(l.right, r.left) and self.helper(l.left, r.right)\n",
    "            \n",
    "        \n",
    "    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n",
    "        return self.helper(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: 'TreeNode') -> 'bool':\n",
    "        # recursive\n",
    "        \n",
    "#         def symmetric(left, right):\n",
    "#             if left and right:\n",
    "#                 return left.val == right.val and symmetric(left.left, right.right) and symmetric(left.right, right.left)\n",
    "#             elif not left and not right:\n",
    "#                 return True\n",
    "#             else:\n",
    "#                 return False\n",
    "    \n",
    "#         if root:\n",
    "#             return symmetric(root.left, root.right)\n",
    "#         else:\n",
    "#             return True\n",
    "        \n",
    "        # iterative\n",
    "        stack_l, stack_r = [], []\n",
    "        if root:\n",
    "            stack_l.append(root)\n",
    "            stack_r.append(root)\n",
    "            while stack_l:\n",
    "                node_l, node_r = stack_l.pop(-1), stack_r.pop(-1)\n",
    "                if node_l.val != node_r.val:\n",
    "                    return False\n",
    "                if node_l.left:\n",
    "                    if node_r.right:\n",
    "                        stack_l.append(node_l.left)\n",
    "                        stack_r.append(node_r.right)\n",
    "                    else:\n",
    "                        return False\n",
    "                elif node_r.right:\n",
    "                    return False\n",
    "                if node_l.right:\n",
    "                    if node_r.left:\n",
    "                        stack_l.append(node_l.right)\n",
    "                        stack_r.append(node_r.left)\n",
    "                    else:\n",
    "                        return False\n",
    "                elif node_r.left:\n",
    "                    return False\n",
    "                \n",
    "        return True\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: 'TreeNode') -> 'bool':\n",
    "        # recursive\n",
    "        \n",
    "        def symmetric(left, right):\n",
    "            if left and right:\n",
    "                return left.val == right.val and symmetric(left.left, right.right) and symmetric(left.right, right.left)\n",
    "            elif not left and not right:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "    \n",
    "        if root:\n",
    "            return symmetric(root.left, root.right)\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.symmetric(root, root)\n",
    "\n",
    "    def symmetric(self, left, right):\n",
    "        if left is None and right is None:\n",
    "            return True\n",
    "        if left is None or right is None:\n",
    "            return False\n",
    "        if left.val != right.val:\n",
    "            return False\n",
    "        else:\n",
    "            return self.symmetric(left.left, right.right) and self.symmetric(\n",
    "                left.right, right.left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def isS(n1,n2):\n",
    "            if n1 == None and n2 == None:\n",
    "                print(\"none\")\n",
    "                return True\n",
    "            if n1 and n2 and n1.val==n2.val:\n",
    "                print(n1.val,n2.val)\n",
    "                return isS(n1.left,n2.right) and isS(n1.right,n2.left)\n",
    "            return False\n",
    "        if root == None:\n",
    "            return True\n",
    "        return isS(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # def isEqual(self, n: TreeNode) -> bool:\n",
    "    #     if not n.left\n",
    "    #     return isEqual(n.left) and is Equal(n.right)\n",
    "    def isEqual(self, n1: TreeNode, n2: TreeNode) -> bool:\n",
    "        # 对于给定的2颗树，判断其结构是否对称\n",
    "        if not n1 and not n2:\n",
    "            return True\n",
    "        if not (n1 and n2):\n",
    "            return False\n",
    "        if not n1.left and n2.right:\n",
    "            return False\n",
    "        if not n1.right and n2.left:\n",
    "            return False\n",
    "        if n1.left and not n2.right:\n",
    "            return False\n",
    "        if n1.right and not n2.left:\n",
    "            return False\n",
    "        # 若结构堆成，则判断该节点的值及递归判断其子树是否对称\n",
    "        return n1.val == n2.val and self.isEqual(n1.left, n2.right) and self.isEqual(n1.right, n2.left)\n",
    "        \n",
    "        \n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        return self.isEqual(root.left, root.right)\n",
    "        \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=101 lang=python3\n",
    "#\n",
    "# [101] 对称二叉树\n",
    "#\n",
    "# https://leetcode-cn.com/problems/symmetric-tree/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (42.80%)\n",
    "# Total Accepted:    16.1K\n",
    "# Total Submissions: 37.6K\n",
    "# Testcase Example:  '[1,2,2,3,4,4,3]'\n",
    "#\n",
    "# 给定一个二叉树，检查它是否是镜像对称的。\n",
    "# \n",
    "# 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。\n",
    "# \n",
    "# ⁠   1\n",
    "# ⁠  / \\\n",
    "# ⁠ 2   2\n",
    "# ⁠/ \\ / \\\n",
    "# 3  4 4  3\n",
    "# \n",
    "# \n",
    "# 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:\n",
    "# \n",
    "# ⁠   1\n",
    "# ⁠  / \\\n",
    "# ⁠ 2   2\n",
    "# ⁠  \\   \\\n",
    "# ⁠  3    3\n",
    "# \n",
    "# \n",
    "# 说明:\n",
    "# \n",
    "# 如果你可以运用递归和迭代两种方法解决这个问题，会很加分。\n",
    "# \n",
    "#\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    #Recursive\n",
    "    # def isSymmetric(self, root):\n",
    "    #     \"\"\"\n",
    "    #     :type root: TreeNode\n",
    "    #     :rtype: bool\n",
    "    #     \"\"\"\n",
    "    #     return self.isMirror(root,root)\n",
    "\n",
    "    \n",
    "    # def isMirror(self,t1,t2):\n",
    "    #     if t1 == None and t2 == None:\n",
    "    #         return True\n",
    "    #     if t1 == None and t2 != None or t1 != None and t2 == None:\n",
    "    #         return False\n",
    "    #     else:\n",
    "    #         return t1.val == t2.val and self.isMirror(t1.left,t2.right) and self.isMirror(t1.right,t2.left)\n",
    "\n",
    "    def isSymmetric(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        import queue\n",
    "        q = queue.Queue()\n",
    "        q.put(root)\n",
    "        q.put(root)\n",
    "        while not q.empty():\n",
    "            t1 = q.get()\n",
    "            t2 = q.get()\n",
    "            if t1 == None and t2 == None:\n",
    "                continue\n",
    "            if t1 == None and t2 != None or t1 != None and t2 == None:\n",
    "                return False\n",
    "            if t1.val != t2.val:\n",
    "                return False\n",
    "            q.put(t1.left)\n",
    "            q.put(t2.right)\n",
    "            q.put(t1.right)\n",
    "            q.put(t2.left)\n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def isSymmetric(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        def check(left, right):\n",
    "            if not (left or right):\n",
    "                return True\n",
    "            if not (left and right):\n",
    "                return False\n",
    "            if left.val != right.val:\n",
    "                return False\n",
    "            return check(left.left,right.right) and check(left.right,right.left)\n",
    "        return check(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\n",
    "        d = []\n",
    "        d.append(root)\n",
    "        d.append(root)\n",
    "        while d:\n",
    "            n1 = d.pop(0)\n",
    "            n2 = d.pop(0)\n",
    "            if not n1 and not n2: continue\n",
    "            if not n1 or not n2: return False\n",
    "            if n1.val != n2.val: return False\n",
    "            d.append(n1.left)\n",
    "            d.append(n2.right)\n",
    "            d.append(n1.right)\n",
    "            d.append(n2.left)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def issym(self,p,q):\n",
    "        if(not p or not q):\n",
    "            if(not p and not q):\n",
    "                return True\n",
    "            return False\n",
    "        else:\n",
    "            if(p.val == q.val):\n",
    "                if(self.issym(p.left,q.right) and self.issym(p.right,q.left)):\n",
    "                    return True\n",
    "                return False\n",
    "            return False\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\n",
    "        if(root == None):\n",
    "            return True\n",
    "        else:\n",
    "            return self.issym(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\r\n",
    "        def check(leftchild, rightchild):\r\n",
    "            if leftchild==None and rightchild==None:\r\n",
    "                return True\r\n",
    "            elif leftchild==None or rightchild==None:\r\n",
    "                return False\r\n",
    "            elif leftchild.val != rightchild.val:\r\n",
    "                return False\r\n",
    "            return check(leftchild.left, rightchild.right) and check(leftchild.right, rightchild.left)\r\n",
    "        if root == None:\r\n",
    "            return True\r\n",
    "        else:\r\n",
    "            return check(root.left, root.right)\r\n",
    "                    \r\n",
    "                    \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\r\n",
    "        if not root:\r\n",
    "            return True\r\n",
    "        queue = []\r\n",
    "        queue.append(root.left)\r\n",
    "        queue.append(root.right)\r\n",
    "        while queue:\r\n",
    "            n1 = queue.pop(0)\r\n",
    "            n2 = queue.pop(0)\r\n",
    "            if not n1 and not n2:\r\n",
    "                continue\r\n",
    "            if not n1 or not n2:\r\n",
    "                return False\r\n",
    "            if n1.val != n2.val:\r\n",
    "                return False\r\n",
    "            queue.append(n1.left)\r\n",
    "            queue.append(n2.right)\r\n",
    "            queue.append(n1.right)\r\n",
    "            queue.append(n2.left)\r\n",
    "        return True            \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return True\n",
    "        return self.mirrorVisit(root.left, root.right)\n",
    "\n",
    "    def mirrorVisit(self, left, right):\n",
    "        if left is None and right is None:\n",
    "            return True\n",
    "        try:\n",
    "            if left.val == right.val:\n",
    "                if self.mirrorVisit(left.left, right.right) and self.mirrorVisit(left.right, right.left):\n",
    "                    return True\n",
    "            return False\n",
    "        except:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if self.isSame(root.left, self.mirror(root.right)):\n",
    "            return True\n",
    "        return False\n",
    "    def mirror(self, root: TreeNode) -> TreeNode:\n",
    "        if root:\n",
    "            root.left, root.right = self.mirror(root.right), self.mirror(root.left)\n",
    "        return root\n",
    "    def isSame(self, root1: TreeNode, root2: TreeNode) -> bool:\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        if not root1 or not root2:\n",
    "            return False\n",
    "        if root1.val != root2.val:\n",
    "            return False\n",
    "        return self.isSame(root1.left, root2.left) and self.isSame(root1.right, root2.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\n",
    "        return self.isSymmetricRecursion(root, root)\n",
    "\n",
    "    def isSymmetricRecursion(self, tree1: TreeNode, tree2: TreeNode) -> bool:\n",
    "        if not tree1 and not tree2: return True  # 两树都空\n",
    "        if not tree1 or not tree2: return False  # 有一棵空\n",
    "\n",
    "        return tree1.val == tree2.val and self.isSymmetricRecursion(tree1.right, tree2.left) and self.isSymmetricRecursion(tree1.left,\n",
    "                                                                                                         tree2.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\n",
    "        flag = [1]\n",
    "\n",
    "        def match(p, q):\n",
    "            if p == None or q == None:\n",
    "                if p == None and q == None:\n",
    "                    return\n",
    "                else:\n",
    "                    flag[0] = 0\n",
    "                    return\n",
    "            if p.val != q.val:\n",
    "                flag[0] = 0\n",
    "                return\n",
    "            match(p.left, q.right)\n",
    "            match(p.right, q.left)\n",
    "            return\n",
    "        if root == None:\n",
    "            return True\n",
    "\n",
    "        match(root.left, root.right)\n",
    "        if flag[0] == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "\n",
    "        left_list = self.bfs_left(root)\n",
    "        right_list = self.bfs_right(root)\n",
    "        left_list = [node.val if node is not None else None for node in left_list]\n",
    "        right_list = [node.val if node is not None else None for node in right_list]\n",
    "        if left_list == right_list:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def bfs_left(self, root: TreeNode) -> list:\n",
    "        bfs_list = list()\n",
    "        bfs_queue = list()\n",
    "        bfs_queue.append(root)\n",
    "        while bfs_queue:\n",
    "            bfs_queue = self.bfs_left_step(bfs_queue)\n",
    "            bfs_list.append(bfs_queue[0])\n",
    "            bfs_queue.pop(0)\n",
    "\n",
    "        return bfs_list\n",
    "\n",
    "    def bfs_right(self, root: TreeNode) -> list:\n",
    "        bfs_list = list()\n",
    "        bfs_queue = list()\n",
    "        bfs_queue.append(root)\n",
    "        while bfs_queue:\n",
    "            bfs_queue = self.bfs_right_step(bfs_queue)\n",
    "            bfs_list.append(bfs_queue[0])\n",
    "            bfs_queue.pop(0)\n",
    "\n",
    "        return bfs_list\n",
    "\n",
    "    def bfs_left_step(self, bfs_queue: list) -> list:\n",
    "        node = bfs_queue[0]\n",
    "        if node is None:\n",
    "            return bfs_queue\n",
    "        bfs_queue.append(node.left)\n",
    "        bfs_queue.append(node.right)\n",
    "        return bfs_queue\n",
    "\n",
    "    def bfs_right_step(self, bfs_queue: list) -> list:\n",
    "        node = bfs_queue[0]\n",
    "        if node is None:\n",
    "            return bfs_queue\n",
    "        bfs_queue.append(node.right)\n",
    "        bfs_queue.append(node.left)\n",
    "        return bfs_queue\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\n",
    "        from collections import deque\n",
    "        queue=deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            if queue==deque([None]*len(queue)):\n",
    "                break\n",
    "            count=len(queue)\n",
    "            print(count)\n",
    "            list=[]\n",
    "            while count>0:\n",
    "                print(queue)\n",
    "                node=queue.popleft()\n",
    "                if node:\n",
    "                    list.append(node.val)\n",
    "                    queue+=(node.left,node.right)\n",
    "                else:\n",
    "                    list.append(None)\n",
    "                count-=1\n",
    "            if list!=list[::-1]:\n",
    "                return False  \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        def dfs(queue):\n",
    "            judge = []\n",
    "            value=[]\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    judge.append(node.left)\n",
    "                    value.append(node.left.val)\n",
    "                else:\n",
    "                    value.append(\"N\")\n",
    "                if node.right:\n",
    "                    judge.append(node.right)\n",
    "                    value.append(node.right.val)\n",
    "                else:\n",
    "                    value.append(\"N\")\n",
    "            for i in range(int(len(value) / 2)):\n",
    "                if value[i] != value[-i - 1]:\n",
    "                    return False\n",
    "            if judge == []:\n",
    "                return True\n",
    "            if not dfs(copy.deepcopy(judge)):\n",
    "                return False\n",
    "            return True\n",
    "        return dfs([root])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def check(self,left,right):\n",
    "        if left == None and right == None:\n",
    "            return True\n",
    "        \n",
    "        if left == None or right == None:\n",
    "            return False\n",
    "        \n",
    "        return left.val == right.val and self.check(left.left,right.right) and self.check(left.right,right.left)\n",
    "        \n",
    "\n",
    "    def isSymmetric(self, root: TreeNode) -> bool:\n",
    "        if not root or  not (root.left or root.right):\n",
    "            return True\n",
    "        \n",
    "        queue = [root.left,root.right]\n",
    "        \n",
    "        while len(queue) > 0:\n",
    "            node_left = queue.pop(0)\n",
    "            node_right = queue.pop(0)\n",
    "            \n",
    "            if not (node_left or node_right):\n",
    "                continue\n",
    "            \n",
    "            if not (node_left and node_right):\n",
    "                return False\n",
    "            \n",
    "            if node_left.val != node_right.val:\n",
    "                return False\n",
    "            \n",
    "            queue.append(node_left.left)\n",
    "            queue.append(node_right.right)\n",
    "            \n",
    "            queue.append(node_left.right)\n",
    "            queue.append(node_right.left)\n",
    "            \n",
    "        return True\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        def traverse(node1, node2):\n",
    "\n",
    "            if not node1 and not node2:\n",
    "                return True\n",
    "\n",
    "            if not node1 and node2:\n",
    "                return False\n",
    "\n",
    "            if not node2 and node1:\n",
    "                return False\n",
    "\n",
    "            if node1.val != node2.val:\n",
    "                return False\n",
    "\n",
    "            return traverse(node1.left, node2.right) and traverse(node1.right, node2.left)\n",
    "\n",
    "        return traverse(root, root)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n",
    "        #利用栈模拟连个左右子树的节点遍历\n",
    "        #分别判断左右子树的内外侧是否相等，相等则成功出栈，其余单边空或不相等情况下为False\n",
    "        if not root:\n",
    "            return True\n",
    "        st = [] #这里改成了栈\n",
    "        st.append(root.left)\n",
    "        st.append(root.right)\n",
    "        while st:\n",
    "            rightNode = st.pop()\n",
    "            leftNode = st.pop()\n",
    "            if not leftNode and not rightNode:\n",
    "                continue\n",
    "            if not leftNode or not rightNode or leftNode.val != rightNode.val:\n",
    "                return False\n",
    "            st.append(leftNode.left)\n",
    "            st.append(rightNode.right)\n",
    "            st.append(leftNode.right)\n",
    "            st.append(rightNode.left)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n",
    "        #利用队列模拟连个左右子树的节点遍历\n",
    "        #分别判断左右子树的内外侧是否相等，相等则成功出队，其余单边空或不相等情况下为False\n",
    "        if not root: return True\n",
    "\n",
    "        from collections import deque\n",
    "        que = deque([root.left, root.right])\n",
    "\n",
    "        while que:\n",
    "            node1 = que.popleft()\n",
    "            node2 = que.popleft()\n",
    "            #该对节点均为空，达标，继续后续节点判断\n",
    "            if not node1 and not node2: continue\n",
    "            #至少一个节点不为空\n",
    "            if not node1 or not node2 or node1.val != node2.val: return False\n",
    "            #两边节点值相等，达标，将node1,node2的两对子节点入队\n",
    "            que.append(node1.left)\n",
    "            que.append(node2.right)\n",
    "            que.append(node1.right)\n",
    "            que.append(node2.left)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    #根-左-右\n",
    "    def pre_order_left(self,root,tlist,flag,cnt=0):     \n",
    "        if not root:\n",
    "            return tlist\n",
    "        tlist.append(str(root.val)+flag+str(cnt))\n",
    "        cnt += 1\n",
    "        self.pre_order_left(root.left,tlist,'L',cnt)\n",
    "        self.pre_order_left(root.right,tlist,'R',cnt)    \n",
    "    #根-右-左\n",
    "    def pre_order_right(self,root,tlist,flag,cnt=0):     \n",
    "        if not root:\n",
    "            return tlist\n",
    "        tlist.append(str(root.val)+flag+str(cnt))\n",
    "        cnt += 1\n",
    "        self.pre_order_right(root.right,tlist,'L',cnt)\n",
    "        self.pre_order_right(root.left,tlist,'R',cnt)       \n",
    "\n",
    "    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n",
    "        num = 0\n",
    "        idx = 0\n",
    "        list_l = []\n",
    "        list_r = []\n",
    "        flag = ''\n",
    "        print(list_l)\n",
    "        self.pre_order_left(root.left,list_l,flag)\n",
    "        print(list_l)\n",
    "        self.pre_order_right(root.right,list_r,flag)\n",
    "        print(list_r)\n",
    "        if list_l == list_r:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n",
    "        def reverse(node):\n",
    "            if node is None: return node\n",
    "            t = node.left\n",
    "            node.left = reverse(node.right)\n",
    "            node.right = reverse(t)\n",
    "            return node\n",
    "        \n",
    "        def isSame(node1, node2):\n",
    "            if node1 is None or node2 is None:\n",
    "                return node1 is None and node2 is None\n",
    "            return node1.val == node2.val and isSame(node1.left, node2.left) and isSame(node1.right, node2.right)\n",
    "        \n",
    "        return isSame(root, reverse(deepcopy(root)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def compare(self, left: Optional[TreeNode], right:Optional[TreeNode]) -> bool:\n",
    "        if  not left and not right:\n",
    "            return True\n",
    "        elif (left and  not right) or ( not left and right) or left.val != right.val:\n",
    "            return False\n",
    "        bool_is_inner_same = self.compare(left.right,right.left)\n",
    "        bool_is_outer_same = self.compare(right.right,left.left)\n",
    "        return bool_is_inner_same and bool_is_outer_same\n",
    "\n",
    "    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        return self.compare(root.left,root.right)\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(L, R):\n",
    "            if not L and not R:\n",
    "                return True\n",
    "            if not L or not R or L.val != R.val:\n",
    "                return False\n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "        return recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n",
    "        return self.dfs(root.left,root.right)\n",
    "\n",
    "\n",
    "    def dfs(self,p,q):\n",
    "        # 终止条件\n",
    "        if not p and not q: return True # 两个空\n",
    "        elif not p or not q: return False # 一个空，一个不空\n",
    "        elif p.val!=q.val: return False # 两个都不空，但是值不相等\n",
    "        else:\n",
    "            # 单层\n",
    "            a = self.dfs(p.left,q.right)\n",
    "            b = self.dfs(p.right,q.left)\n",
    "            return a and b"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
